1. Field of the Invention
The present invention generally relates to wireless communication systems. More particularly, the present invention relates to providing secure communications in ad-hoc wireless communication systems. Even more particularly, the present invention relates to generating keys in wireless communication systems.
2. Background
The broadcast nature of a wireless link provides a natural eavesdropping and intervention capability to an adversary. Thus, securing a wireless link is essential to the security of a wireless network, and key generation algorithms are used for securing wireless links. However, traditional key agreement algorithms can be very costly and/or unsuitable in many settings, e.g., in wireless ad-hoc networks, since they consume scarce resources such as bandwidth and battery power.
Currently, there does not exist a one-size-fits-all key management scheme for all wireless networks. Conventional solutions depend on the network architecture, existence of trusted third parties, available resources on wireless clients and the capabilities of adversaries. In conventional ad-hoc wireless networks having a plurality of communication nodes, the general approach is to equip each node with either (i) a master key, or (ii) a list of keys (a key-chain), or (iii) keying materials. This way a pair of wireless nodes can either find or generate a key in common. Further, conventional systems include master key based solutions, where wireless nodes are pre-distributed with a master key. In this case, two nodes first exchange random “nonces” or node IDs and use the master key along with a pseudo random function to generate a symmetric session key. In the conventional key-chain based solutions, each wireless node is pre-distributed with a list of keys, called a key-chain. In these systems, two nodes exchange their list of key IDs and use a combination of common keys as the symmetric session key. In such systems, key-chains must be carefully designed so that either two nodes have a key in common in their key-chains and they have a wireless link between them, or there is a path, called a key-path, among these two nodes where each pair of neighboring nodes on this path have a key in common.
Algorithms for generating key-chains fall into the following classes:                (i) probabilistic class, where key-chains are randomly selected among a pool of keys;        (ii) deterministic class, where key chains are designed from a set of keys by using algorithms such as Balanced Incomplete Block Design (“BIBD”) of design theory (e.g., Camtepe, S. A., et al., “Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks”, in Samarati et al. (eds.), Computer Security-ESORCIS, Springer-Verlag, LNCS 3193, 2004; Camtepe, S. A., et al., “Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks”, ACM/IEEE Transactions on Networks, 2007; Camtepe, S. A., et al., “Expander Graph Based Key Distribution Mechanisms in Wireless Sensor Networks”, IEEE Int. Conf. on Commun., 2006); and        (iii) hybrid probabilistic and deterministic class.        
In dynamic key generation solutions, a set of public and private keying materials is formed in a probabilistic, deterministic or hybrid manner and is pre-distributed to each wireless node. Two nodes exchange their public information such as node ID in a polynomial-based solution or a public column vector in matrix-based solution. The concept of combining key management and physical layer characteristics is first presented in Hershey, J. E., et al., “Unconventional Cryptographic Keying Variable Management”, IEEE Transaction on Communications, January 1995 vol. 43, no. 1, pp. 3-6. Some conventional systems use steerable parasitic array radiator antennae requiring ubiquitous and cheap omni-directional antennae. Further, this method relies on strict reciprocity, without allowing for more distortion than noise and differences in transmission powers. In a real network, the most pernicious presence causing distortion is interference, not noise, which is often on the order of magnitude lower than interference. However, this method breaks down reciprocity and focuses on the entire signal envelope. Other conventional approaches use communications between a user terminal and an access point and require steerable parasitic array radiator antennae. In addition to the special antenna, this technique requires overhead bandwidth expenditure in that an access point must transmit a constant amplitude wave, which serves no purpose other than generating the key. Once again, strict reciprocity is required for the uplink and downlink signal profiles to match. In a practical setting with interference present, that simply will not be available. Another conventional method is based on the time-varying frequency characteristics, and is suitable for orthogonal frequency division multiplexing (“OFDM”) systems. This method utilizes channel reciprocity and time-variant frequency characteristics to generate a security key. It also measures time difference compensation of the channel and uses a synchronous addition process for noise reduction to prevent errors in key generation. This approach is expensive and sensitive to estimation errors. Conventional systems, described above, add message exchanges, special antennas, strict reciprocity assumptions, and limit themselves to ultra-wideband (“UWB”) communications.